﻿#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	
};

class Solution {
public:
	struct cmp {
		bool operator()(pair<int, int>& a, pair<int, int>& b) {
			return a.second > b.second;
		}
	};
	//static bool cmp(pair<int, int>& a, pair<int, int>& b) {
		//return a.second > b.second;
	//}
	vector<int> topKFrequent(vector<int>& nums, int k) {
		unordered_map<int, int> map;
		priority_queue < pair<int, int>, vector<pair<int, int>>, cmp>  q;
		vector<int> ans;
		for (int i = 0; i < nums.size(); i++) {
			map[nums[i]]++;
		}
		auto it = map.begin();
		while (it != map.end()) {
			if (q.size() < k)
				q.emplace(it->first, it->second);
			else if(q.top().second<it->second){
				q.pop();
				q.emplace(it->first, it->second);
			}
			it++;
		}
		while (!q.empty()) {
			ans.emplace_back(q.top().first);
			q.pop();
		}
		return ans;
	}
};

int main()
{ 
	Solution sol;
	vector<int> test = { 5,3,1,1,1,3,73,1 };
	sol.topKFrequent(test, 2);
	cout <<endl;
}
